package LeetCode;

public class LC_576_OutofBoundaryPaths {

    public static void main(String[] args) {

    }

    public class Solution {
        public int findPaths(int m, int n, int N, int a, int b) {
            if (N <= 0) return 0;
            int[][] cnt = new int[m][n];
            int res = 0;
            int mod = 1000000007;
            int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            cnt[a][b] = 1;
            for (int i = 0; i < N; i++) {
                int[][] temp = new int[m][n];
                for (int j = 0; j < m; j++) {
                    for (int k = 0; k < n; k++) {
                        for (int[] dir : dirs) {
                            int nm = j + dir[0];
                            int nn = k + dir[1];
                            if (nm < 0 || nn < 0 || nm >= m || nn >= n) res = (res + cnt[j][k]) % mod;
                            else temp[nm][nn] = (temp[nm][nn] + cnt[j][k]) % mod;
                        }
                    }
                }
                cnt = temp;
            }
            return res;
        }
    }

}